package subString;

import org.junit.Test;

import java.util.HashMap;

/**
 * @className: LeetCode_560
 * @Description: 统计序列中和为k的连续子数组的个数
 * @author: kunkun
 * @date: 2025/3/2 21:14
 */
public class LeetCode_560 {
    public int subarraySum(int[] nums, int k) {
        results = new Integer[nums.length][nums.length];
        initNums();
//        return solution_1(nums,k,0,nums.length-1);
//        return solution_2(nums,k,0,nums.length-1);
//        return solution_3(nums,k);
//        return solution_4(nums,k);
        return solution_5(nums,k);
    }


    @Test
    public void test(){
        System.out.println(subarraySum(new int[]{1,1,1},2));    //2
        System.out.println(subarraySum(new int[]{1,2,3},3));    //2
        System.out.println(subarraySum(new int[]{1,-1,0},0));   //3
    }


    public void initNums(){
        for (int i = 0; i < results.length; i++) {
            for (int j = 0; j < results[i].length; j++) {
                results[i][j]=null;
            }
        }
    }

    /**
     * @Author kunkun
     * @Description 方法1：使用递归求解，超时，时间复杂度：O（3^n）,空间复杂度：O（n）
     * @Date 21:22 2025/3/2
     * @Param left：左边界
     * @Param right：右边界
     * @return
     **/
    public static int solution_1(int[] nums, int k,int left,int right){
        //1. 特殊情况
        if (left > right){
            return 0;
        }
        //2. 命中
        int sum = subNums(nums,left,right);
        return ((sum==k)?1:0)+solution_1(nums,k,left+1,right)
                +solution_1(nums, k, left, right-1)
                -solution_1(nums, k, left+1, right-1);
    }


    static Integer[][] results ;
    /**
     * @Author kunkun
     * @Description 方法2：利用二维数组存储结果，以空间换时间，时间复杂度：O（n^2）,空间复杂度：O（n^2）
     * @Date 21:22 2025/3/2
     * @Param left：左边界
     * @Param right：右边界
     * @return
     **/
    public static int solution_2(int[] nums, int k,int left,int right){
        //1. 特殊情况
        if (left > right){
            return 0;
        }
        //2. 缓存判断
        if (results[left][right]!=null){
            return results[left][right];
        }
        //3. 命中+计算结果
        int sum = subNums(nums,left,right);
        int result = ((sum==k)?1:0)+solution_1(nums,k,left+1,right)
                +solution_1(nums, k, left, right-1)
                -solution_1(nums, k, left+1, right-1);
        results[left][right]= result;
        return result;
    }

    /**
     * @Author kunkun
     * @Description 方法3：动态规划，时间复杂度：O（n^2）,空间复杂度：O（n^2）
     * @Date 21:22 2025/3/2
     * @Param left：左边界
     * @Param right：右边界
     * @return
     **/
    public static int solution_3(int[] nums, int k){
        //1. 基础值赋值
        for (int i = 0; i < results.length; i++) {
            for (int j = 0; j < results[i].length; j++) {
                if (i>j){
                    results[i][j]=0;
                }
            }
        }

        //2. 计算前缀和
        int[] sums = new int[nums.length];
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            sums[i]=sum;
        }

        //2. 逐斜线填值
        for (int line = 0; line < results.length; line++) {
            for (int i=0,j=line; j < results.length; i++,j++) {
                int tempSum = subNumsPrex(sums,i,j);
                results[i][j] = ((tempSum==k)?1:0)
                        + ((i+1 >= results.length)?0:results[i+1][j])
                        + ((j-1<0)?0:results[i][j-1])
                        - ((j-1<0 || i+1>=results.length)?0:results[i+1][j-1]);
            }
        }
        return results[0][results.length-1];
    }

    /**
     * @Author kunkun
     * @Description 方法4：使用前缀和+双重递归的方式求解，时间复杂度：O（n^2）,空间复杂度：O（1）
     * @Date 22:48 2025/3/2
     * @Param
     * @return
     **/
    public static int solution_4(int[] nums, int k){
        //1. 计算前缀和
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            nums[i]=sum;
        }
        //2. 计算总次数
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (subNumsPrex(nums,i,j)==k){
                    result++;
                }
            }
        }
        return result;
    }

    /**
     * @Author kunkun
     * @Description 方法4：使用前缀和+哈希表的方式求解，时间复杂度：O（n）,空间复杂度：O（n）
     * @Date 22:48 2025/3/2
     * @Param
     * @return
     **/
    public static int solution_5(int[] nums, int k){
        //1. 定义哈希表
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);       //记录为0情况，及为后续的计算总次数算本身
        int result = 0,preSum = 0;
        //2. 遍历数组
        for (int num : nums) {
            preSum+=num;
            result+=map.getOrDefault(preSum-k,0);
            map.put(preSum,map.getOrDefault(preSum,0)+1);
        }

        return result;
    }


    //字串求和函数--蛮力
    public static int subNums(int[] nums, int left,int right){
        int sum=0;
        for (int i = left; i <= right; i++) {
            sum+=nums[i];
        }
        return sum;
    }

    //字串求和函数--前缀和
    public static int subNumsPrex(int[] nums, int left,int right){
        int sum=0;
        if (left==0){
            return nums[right];
        }
        return nums[right]-nums[left-1];
    }


}
